package arithmetic.monoton;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 单调栈, 维护一个数组,使得元素每一个位置存的是当前左边的最大值.
 *
 *  作用： 用O(n)的时间复杂度 计算出 左右两边第一个比自己小或者大的数。
 *  右边第一个比自己大、小的数 谁让我出栈就是谁。
 *  左边第一个比自己小、大的数，我出栈时压着的是谁，就是第一个比我
 *
 * 经典案例:接雨水问题. 计算最大矩形面积
 * @author jiangfeng on 2022/4/28
 *
 *
 */
public class MonotonStack {

    /**
     *
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(monon(new int[]{2,4,1,4,6,3}));  // 1,1,1,3,3,3    // 2,2,1,1,4,1
        //
    }

    public static List<Integer> monon(int[] a){
        List<Integer> list =new ArrayList<>();
        Stack<Integer> st = new Stack<>();
        int[] b = new int[a.length];
        int[] c = new int[a.length];
        // 单调递增栈， 谁让他出谁是右边第一个比他小, 他压着的是左边第一个比他小

        st.push(0);
        int i =1;
        while (i<a.length){
            while (st.isEmpty()||(i<a.length && a[st.peek()]<a[i])){
                st.push(i++);
            }
            while (!st.isEmpty() && i<a.length && a[st.peek()]>= a[i] ){
                int d  = st.pop();
                b[d] = a[i];
                c[d] = a[st.empty()?d:st.peek()];
                list.add(a[d]);
            }
        }
        // 最后全部出栈.
        while (!st.isEmpty()){
            int d = st.pop();
            list.add(a[d]);
            // 没有比他更小的，就是他本身了。
            b[d]=a[d];

            c[d] = a[st.empty()?d:st.peek()];
        }
        System.out.println(Arrays.toString(b));
        System.out.println(Arrays.toString(c));
        return list;




    }
}
